import com.sun.xml.internal.bind.v2.model.core.MaybeElement;

import java.net.MalformedURLException;

/**
 * Created by L.jp
 * Description:给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
 *
 * User: 86189
 * Date: 2023-03-21
 * Time: 1:35
 */
public class Solution {
    public int maxProfit(int[] prices) {
        //贪心思想，要求局部最小值
        //先找出最小值
        /*int minValue=prices[0];
        int profit=0;
        for(int i = 1; i < prices.length; i++) {
            minValue=Math.min( prices[i],minValue );
            //当前值减去最小值和前一天的最大利润，哪个更大就是最大利润
            profit= Math.max( prices[i]-minValue,profit );
        }
        return profit;*/
        
        //动态规划思想
        int[] dp=new int[prices.length]; //dp[i]表示第i+1天的最大利润，因为i=0时没有
        int minVal=prices[0];
        for(int i=1;i<prices.length; i++){
            minVal= Math.min( prices[i],minVal );
            //最大利润是，前一天的最大利润跟 （当天的最大利润-最小值） 的最大值
            dp[i]=Math.max( dp[i-1],prices[i]-minVal);
        }
        return dp[prices.length-1];
    }
}
